package com.buddy.summary.code.algorithm;

import java.util.Arrays;

/**
 * 给出一个正整数，找出这个正整数所有数字全排列后的下一个数
 * 在一个整数所包含数字的全部组合后，找到一个大于且等于原数的新整数
 * 如果输入12345，则返回12354
 * 如果输入12354，则返回12435
 * 如果输入12435，则返回12453
 */
public class Algorithm_07 {
    //思路：
    //1.从后向前查看逆序区域，找到逆序区域的前一位，即数字交换的边界
    //2.让逆序区域的前一位和逆序区域中大于它的最小的数字交换位置
    //3.把原来的逆序区域转为顺序状态
    //比如：
    //12354 ——  123 54
    //3和4交换 —— 124 53
    //53转顺序 —— 12435
    private static int[] findNearestNum(int[] nums){
        //1.从后向前查看逆序区域，找到逆序区域的前一位，即数字交换的边界
        int index = findTransferPoint(nums);
        //如果index = 0，说明整个数组已经逆序，无法得到更大整数
        if (index == 0)
            return null;
        //2.把逆序区域的前一位和逆序区域中大于它的最小的数字交换位置
        int[] copyNums = Arrays.copyOf(nums,nums.length);
        exchangeHead(copyNums,index);
        //3.把原来的逆序区域转为顺序状态
        reverse(copyNums,index);
        return copyNums;
    }


    private static int findTransferPoint(int[] nums) {
        for (int i = nums.length -1;i>0;i--){
            if (nums[i] > nums[i-1])
                return i;
        }
        return 0;
    }

    private static int[] exchangeHead(int[] nums, int index) {
        int head = nums[index -1];
        for (int i= nums.length -1;i>=index;i--){
            if (head < nums[i]){
               nums[index - 1] = nums[i];
               nums[i] = head;
               break;
            }
        }
        return nums;
    }

    private static int[] reverse(int[] nums, int index) {
        for (int i=index,j=nums.length -1;i<j;i++,j--){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        return nums;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,4,3,2,1};
        System.out.println(findTransferPoint(nums));
        System.out.println(Arrays.toString(findNearestNum(nums)));

    }
}
